#pragma once

#include "stdafx.h"
#include "Graph.h"

using namespace GraphTools;

namespace MaxWeightStuff
{
	template<class T>
	class MyVector
	{
		vector<T> elems;
	public:
		MyVector()
			: elems(vector<T>()) { }
		MyVector(int size)
			: elems(vector<T>(size)) { }
		MyVector(vector<T> old)
			: elems(old) { }
		int size()
		{
			return elems.size();
		}
		void push_back(const T &elem)
		{
			elems.push_back(elem);
		}
		void pop_back()
		{
			elems.pop_back();
		}
		void reverse()
		{
			std::reverse(elems.begin(), elems.end()); 
		}
		T &operator [](const int b)
		{
			if (b >= 0)
				return elems[b];
			else
			{
				return elems[b + elems.size()];
			}
		}
		vector<T> ToVector()
		{
			return elems;
		}
	};

	class Myboolean
	{
	public:
		Myboolean() : state(false)
		{ }
		Myboolean(bool state) : state(state)
		{ }
		operator bool () const
		{
			return state;
		}
	private:
		bool state;
	};

	class MaxWeightedResolver
	{
	private:
		int iteraaaa;

		int CHECK_DELTA;
		int CHECK_OPTIMUM;

		MyVector<EdmondsEdge> edges;
		int max_weight;
		MyVector<int> endpoint;
		MyVector<MyVector<int>> neighbend;
		MyVector<int> mate;
		MyVector<int> label;
		int nvertex;
		MyVector<int> labelend;
		MyVector<int> inblossom;
		MyVector<int> blossomparent;
		MyVector<MyVector<int>> blossomchilds;
		MyVector<int> blossombase;
		MyVector<MyVector<int>> blossomdps;
		MyVector<int> bestedge;
		MyVector<MyVector<int>> blossombestedges;
		MyVector<int> unusedblossoms;
		MyVector<int> dualvar;
		MyVector<Myboolean> allowedge;
		MyVector<int> _queue;
		int nedge;


		int slack(int k);
		MyVector<int> blossomLeaves(int b);
		void assignLabel(int w, int t, int p);
		int scanBlossom(int v, int w);
		void addBlossom(int base, int k);
		void expandBlossom(int b, bool endstage);
		void augmentBlossom(int b, int v);
		void augmentMatching(int k);
		void verifyOptimum();
		void checkDelta2();
		void checkDelta3();
	public:
		MaxWeightedResolver();
		vector<int> MaxWeightedMatching(vector<EdmondsEdge> this_edges);
	};
};

//using namespace MaxWeightStuff;

namespace SiloachReducer
{
	class DCWMSResolver
	{
	private:
		vector<EdmondsEdge> OriginalEdges;
		int Degree;
		int VertexCounter;
		int OriginalVertexCount;
		vector<EdmondsEdge> TransformedGraph;
		//vector<int> riferimenti;
	public:
		DCWMSResolver(int vertexCount, vector<EdmondsEdge> edges, int degree);
		vector<pair<int, int>> Resolve();
	};
}

